package LearnDataStructure.a_线性结构.例题;

import java.util.Stack;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-03 18:41
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.a_线性结构.例题
 */
/*
无论这个链表是奇数还是偶数
 */
public class g_判断单向链表整体是否回文 {
    public static void main(String[] args) {
        g_判断单向链表整体是否回文 test = new g_判断单向链表整体是否回文();
        int[] arr = new int[] {1,2,3,2,1};
        int[] arr2 = new int[] {1,2,3,3,2,1};
        int[] arr3 = new int[] {1,2,4,3,2,1};
        test.useCheckLoop(arr3);
    }

    public void useCheckLoop(int[] arr) {
        CaseNode head = new CaseNode(arr[0]);
        CaseNode p = head;
        for (int i = 1; i < arr.length; i++) {
            p.next = new CaseNode(arr[i]);
            p = p.next;
        }
        boolean b = checkLoop(head);
        System.out.println(b);
    }

    public boolean checkLoop(CaseNode head) {
        if (head == null) {//空链表
            return false;
        }
        if (head.next == null) {//单元素链表
            return true;
        }
        CaseNode slow = head;
        CaseNode fast = head;
        boolean isOdd = true;//判断链表节点个数是否为奇数
        Stack<CaseNode> stack = new Stack<CaseNode>();
        while (fast != null && fast.next != null) {
            stack.push(slow);
            slow = slow.next;
            fast = fast.next.next;
            if (fast == null) {//当偶数个节点，才进入这个判断
                isOdd = false;
            }
        }
        if (isOdd) {//奇数节点则还需往前移动一格
            slow = slow.next;
        }
        while (!stack.empty()) {//开始判断回文串，适用于奇数和偶数；具体过程可以自己画图看一看
            if (stack.pop().data != slow.data) {
                return false;
            } else {
                slow = slow.next;
            }
        }
        return true;
    }
}
